package 动态规划;

import java.util.Arrays;

public class LeetCode213_打家劫舍2 {

    public int rob(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        if(nums.length <= 2) {
            Arrays.sort(nums);
            return nums[nums.length-1];
        }
        // 就是看不偷第一个还是不偷最后一个
        return Math.max(robRange(nums, 0, nums.length-1), robRange(nums, 1, nums.length));
    }

    public int robRange(int[] dp, int start, int end) {
        int first = dp[start];
        int second = Math.max(dp[start], dp[start+1]);
        for(int i = start+2; i < end; i++) {
            int temp = second;
            second = Math.max(first + dp[i], second);
            first = temp;
        }

        return second;
    }


}
